package algorithm.middle;

import java.util.*;

public class Rotate48 {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        //转置，即对角线交换
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int a = matrix[i][j];
                int b = matrix[j][i];
                matrix[i][j] = b;
                matrix[j][i] = a;
            }
        }
        //镜像
        for (int i = 0; i < n / 2; i++) {
            for (int row = 0; row < n; row++) {
                int a = matrix[row][i];
                int b = matrix[row][n - i - 1];
                matrix[row][i] = b;
                matrix[row][n - i - 1] = a;
            }
        }
    }


    public boolean canConstruct(String ransomNote, String magazine) {
        int[] arr = new int[128];
        for (int i = 0; i < magazine.length(); i++) {
            arr[magazine.charAt(i)]++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            char c = ransomNote.charAt(i);
            arr[c]--;
            if (arr[c] < 0) {
                return false;
            }
        }
        return true;
    }

    public boolean isIsomorphic(String s, String t) {
        int n = s.length();
        int[] map = new int[128];
        Set<Character> set = new HashSet<>();
        Arrays.fill(map, -1);
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (map[c] == -1) {
                char tc = t.charAt(i);
                if (set.contains(tc)) {
                    return false;
                }
                map[c] = tc;
                set.add(tc);
            } else {
                if (map[c] != t.charAt(i)) {
                    return false;
                }
            }
        }
        return true;
    }

    public List<String> summaryRanges(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        list.add(temp);
        for (int i = 0; i < nums.length; i++) {
            temp.add(nums[i]);
            if (i + 1 < nums.length && nums[i + 1] != nums[i]) {
                temp = new ArrayList<>();
                list.add(temp);
            }
        }
        List<String> res = new ArrayList<>();
        for (List<Integer> arr : list) {
            if (arr.size() == 1) {
                res.add(arr.get(0).toString());
            } else {
                res.add(arr.get(0) + "->" + arr.get(arr.size() - 1));
            }
        }
        return res;
    }

}
